package 二叉树

/*
https://leetcode.cn/problems/binary-tree-level-order-traversal/?envType=study-plan-v2&envId=top-100-liked

102. 二叉树的层序遍历
给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]

示例 2：
输入：root = [1]
输出：[[1]]

示例 3：
输入：root = []
输出：[]
*/

func levelOrder(root *TreeNode) [][]int {
	res := make([][]int, 0)
	if root == nil {
		return res
	}

	q := make([]*TreeNode, 0)
	q = append(q, root)

	temp := make([]int, 0)
	for len(q) > 0 {
		size := len(q)

		for i := 0; i < size; i++ {
			curNode := q[0]
			q = q[1:]

			temp = append(temp, curNode.Val)
			if curNode.Left != nil {
				q = append(q, curNode.Left)
			}
			if curNode.Right != nil {
				q = append(q, curNode.Right)
			}
		}
		res = append(res, temp)
		temp = []int{}
	}

	return res
}
